﻿using System;
using System.Text;

/*
Gemaakt door: Koen Ursem INF2C Groep: Koen, Pascal, Ramon.
Versie 1.0

*/

namespace SkipList
{
    public class SkipList
    {
        /* (key, value) and pointers towards Node situated to the right, upwards and downwards. */
        private class Node
        {
            public Node(IComparable key, object value)
            {
                this.key = key;
                this.value = value;
                this.right = this.up = this.down = null;
            }

            public Node() : this(null, null) { }

            public IComparable key;
            public object value;
            public Node right, up, down;
        }

        /* Public constructor. Parameters the maximum number of paralel lists and the probability. */
        public SkipList(int maxListsCount, double probability)
        {
            this.maxListsCount = maxListsCount;
            this.probability = probability;

            /* Initialize the sentinel nodes for each list. */
            this.head = new Node[maxListsCount + 1];
            for (int i = 0; i <= maxListsCount; i++)
			{
                this.head[i] = new Node();
			}
            this.tail = new Node();

            /* Link the first sentinels of the lists one to another. Also link all head sentinels to the unique tail sentinel. */
            for (int i = 0; i <= maxListsCount; i++)
            {
                head[i].right = tail;
                if (i > 0)
                {
                    head[i].down = head[i - 1];
                    head[i - 1].up = head[i];
                }
            }

            /* For the beginning we have only the bottom list. */
            this.currentListsCount = 0;
        }

        /* public constructor. creates a skip list with 11 aditional lists and a probability of 0.5. */
        public SkipList() : this(11, 0.5) { }

        /* Inserts a pair of (key, value) into the Skip List structure. */
        public void Insert(IComparable key, object value)
        {

            Node[] next = new Node[maxListsCount + 1];

            /* parse the skip list structure. The cursor variable is the current node we reached. */
            Node cursor = head[currentListsCount];
            for (int i = currentListsCount; i >= 0; i--)
            {
                /* If we are not at the topmost list, then we move down one list. */
                if (i < currentListsCount)
                    cursor = cursor.down;

                /* While we do not reach the second sentinel and we do not find a greater numeric value than the one we want to insert, keep moving right. */
                while ((cursor.right != tail) && (cursor.right.key.CompareTo(key) < 0))
				{
                    cursor = cursor.right;
				}
                next[i] = cursor;
            }

            /* If the value exists already overwrite it */
            if ((next[0].right != tail) && (next[0].right.key.Equals(key)))
            {
                next[0].right.value = value;
            }

            /* If the number to insert is not in the list, then we flip the coin and insert it in the lists. */
            else
            {
                /* We find a new level number which will tell us in how many lists to add the new number. This new random level number is generated by flipping a coin. */
                int newLevel = NewRandomLevel();

                /* If the new level is greater than the current number of lists, then we extend our "rightmost nodes" array to include more lists. In the same time we increase the
                 * number of current lists. */
                if (newLevel > currentListsCount)
                {
                    for (int i = currentListsCount + 1; i <= newLevel; i++)
					{
                        next[i] = head[i];
					}
                    currentListsCount = newLevel;
                }
                 /* We add the node starting from the bottom list and moving up to the next lists. When we get above the bottom list, we start updating the "up" and "down" pointers. */
                Node prevNode = null;
                Node n = null;
                for (int i = 0; i <= newLevel; i++)
                {
                    prevNode = n;
                    n = new Node(key, value);
                    n.right = next[i].right;
                    next[i].right = n;
                    if (i > 0)
                    {
                        n.down = prevNode;
                        prevNode.up = n;
                    }
                }
            }
        }

        /* This method computes a random value, smaller than the maximum admitted lists count. This random value will tell us into how many lists to insert a new key. */
        private int NewRandomLevel()
        {
            int newLevel = 0;
            while ((newLevel < maxListsCount) && FlipCoin())
			{
                newLevel++;
			}
            return newLevel;
        }

        /* returns true, or false for probabilty to create a level depth */
        private bool FlipCoin()
        {
            double d = r.NextDouble();
            return (d < this.probability);
        }

        /* This method removes a key from the Skip List structure. */
        public void Remove(IComparable key)
        {
            /* parse each list, starting from the top list and going down towards the bottom list. On each list, we move from the first sentinel node
             * rightwards until either we reach the second sentinel node, either we find a node with a key greater or equal than the key we want to remove.
             * For each list we remember the rightmost node that we reached. */
            Node[] next = new Node[maxListsCount + 1];

            /* We search for the value to remove. We start from the topmost list, from the first sentinel node and move right, down, right, down, etc.
             * As we said above, we will remember for each level the rightmost node that we reach. */
            Node cursor = head[currentListsCount];
			
            for (int i = currentListsCount; i >= 0; i--)
            {
                if (i < currentListsCount)
				{
                    cursor = cursor.down;
				}
                /* Move right as long as we encounter values smaller than the value we want to remove. */
                while ((cursor.right != tail) && (cursor.right.key.CompareTo(key) < 0))
				{
                    cursor = cursor.right;
				}
                /* When we got here, either we reached the second sentinel node on the current level, either we found a node that is not smaller than the value we want to
                 * remove. It is possible that the node we found is equal to the value that we want to remove, or it can be greater. In both cases we will store this rightmost node. */
                next[i] = cursor;
            }

            /* see if it is equal with the value or not. If it is equal, then we remove the value from the bottom list and also from the lists above. */
            if ((next[0].right != tail) && (next[0].right.key.Equals(key)))
            {
                /* Parse each existing list. */
                for (int i = currentListsCount; i >= 0; i--)
                {
                    /* And if the rightmost reached node is followed by the key to remove, then remove the key from the list. */
                    if ((next[i].right != tail) && next[i].right.key.Equals(key))
					{
                        next[i].right = next[i].right.right;
					}
                }
            }
        }


        /* Returns the object associated with that key, or null if the key is not found. */
        public object Find(IComparable key)
        {
            /* We parse the skip list structure starting from the topmost list, from the first sentinel node. As long as we have keys smaller than the key we search for, we keep moving right.
             * When we find a key that is greater or equal that the key we search, then we go down one level and there we try to go again right. When we reach the bottom list, we stop. */
            Node cursor = head[currentListsCount];
            for (int i = currentListsCount; i >= 0; i--)
            {
                if (i < currentListsCount)
				{
                    cursor = cursor.down;
				}

                while ((cursor.right != tail) && (cursor.right.key.CompareTo(key) < 0))
				{
                    cursor = cursor.right;
				}
            }

            /* Now we see if the searched key is there or not. If it is, we return the value associated with it. If not, we return null. */
            if ((cursor.right != tail) && (cursor.right.key.Equals(key)))
			{
                return cursor.right.value;
			}
            else
			{
                return null;
			}
        }

        private Node[] head;
        private Node tail;
        private int maxListsCount;
        private int currentListsCount;
        private double probability;
        private Random r = new Random();
    }
}
